package com.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author durant
 * @create 2021-11-13 8:34
 */
public class InToPolandNotation {
    public static void main(String[] args) {
        String suffixExpression = "1+((2+3)*4)-5";


        List<String> strings = toInfixExpressionList(suffixExpression);
        System.out.println(strings);
        // 将得到的中缀表达式得到的list转给后置表达式的list
        List<String> parseSuffixExpressionList = parseSuffixExpressionList(strings);
        System.out.println(parseSuffixExpressionList);

    }

    public static List<String> parseSuffixExpressionList(List<String> ls) {
        Stack<String> stack1 = new Stack<>();
        List<String> stack2 = new ArrayList<>();//stack2其实用数组可以代替，因为没有出栈的操作，后面有逆序输出的操作
        //遍历数组
        //       2 从左至右扫描中缀表达式；
        //       3 遇到操作数时，将其压s2；
        //       4 遇到运算符时，比较其与s1栈顶运算符的优先级：
        //          1如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
        //          2否则，若优先级比栈顶运算符的高，也将运算符压入s1；
        //          3否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
        //       5遇到括号时：(1) 如果是左括号“(”，则直接压入s1(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
        //       6重复步骤2至5，直到表达式的最右边
        //       7将s1中剩余的运算符依次弹出并压入s2
        //       7依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
        for (String item : ls) {
            if (item.matches("\\d+")) { // 第三步
                stack2.add(item);
            } else if (item.equals("(")) { // 4.1
                stack1.push(item);
            } else if (item.equals(")")) {
//                如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!stack1.peek().equals("(")) {//不是左括号
                    stack2.add(stack1.pop());
                }
                // 当遇到左括号后，需要将左括号弹出
                stack1.pop();

            } else {
                // 当item的优先级小于等于栈顶运算符的优先级 将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
                // 4.3
                while (stack1.size() != 0 && (Operation.getValue(stack1.peek()) >= Operation.getValue(item))){// 栈顶的优先级大于等于 item
                    stack2.add(stack1.pop());// 将s1栈顶的运算符弹出
                }
                // 并压入到s2中
                stack1.push(item);
            }

        }
        while (stack1.size() != 0){
            stack2.add(stack1.pop());
        }
        return stack2;
    }


    // 将一个中缀表达式转换成为对应的List
    public static List<String> toInfixExpressionList(String s) {
        List<String> ls = new ArrayList<>();
        int i = 0;//这是一个指针，用于遍历表达式字符串
        String str; // 对多位数进行拼接
        char c; // 每遍历到一个字符，就放入到c
        do {
            // 如果c是一个非数字，就需要加入到ls中，
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {// 不是一个数
                ls.add("" + c);
                i++;
            } else {// 如果是一个数，那么需要拼接
                str = "";//先置空
                while (i < s.length() && ((c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57)) {
                    str += c;//拼接
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }


}

//返回操作符对应的优先级
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int result;
        switch (operation) {
            case "+":
                result= ADD;
            break;
            case "-":
                result=SUB;
            break;
            case "*":
                result=MUL;
            break;
            case "/":

                result=DIV;
            break;
            default:
                result=0;
            break;
        }
        return result;
    }

}
